class Solution {
    int target;
    int ans = 0;
    public int pathSum(TreeNode root, int targetSum) {
        this.target = targetSum;
        dfs(root, 0, new HashMap<>());
        return ans;
    }

    public void dfs(TreeNode root, int sum, Map<Integer, Integer> prefixSum) {
        if (root == null)
            return;
            
        prefixSum.put(sum, prefixSum.getOrDefault(sum, 0) + 1);
        sum += root.val;
        if (prefixSum.containsKey(sum - target)) {

            ans += prefixSum.get(sum - target);
        }

        dfs(root.left, sum, prefixSum);

        dfs(root.right, sum, prefixSum);

        prefixSum.put(sum-root.val, prefixSum.getOrDefault(sum-root.val, 0) - 1);
    }
}